---
title: "山峰和山谷"
created: 2025-11-28
tags:
  - 算法
---

# 山峰和山谷

## 题目 [山峰和山谷](https://www.acwing.com/solution/content/139758/)

FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。

为了能够对旅程有一个安排，他想知道山峰和山谷的数量。

给定一个地图，为FGD想要旅行的区域，地图被分为 n \* n 的网格，每个格子 (i,j)的高度 w(i,j)是给定的。

若两个格子有公共顶点，那么它们就是相邻的格子，如与 (i,j)(i,j)(i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)

我们定义一个格子的集合 S 为山峰（山谷）当且仅当：

1. S 的所有格子都有相同的高度。
2. S 的所有格子都连通。
3. 对于 s 属于 S，与 s 相邻的 s’不属于 S，都有 ws>ws′（山峰），或者 ws<ws′（山谷）。
4. 如果周围不存在相邻区域，则同时将其视为山峰和山谷。

你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

输入格式

第一行包含一个正整数 nnn，表示地图的大小。

接下来一个 n \* n 的矩阵，表示地图上每个格子的高度 w。

输出格式

共一行，包含两个整数，表示山峰和山谷的数量。

数据范围

![[image-9b7ed371.png]]

输入样例1：

```text
5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8
```

输出样例1：

```text
2 1
```

输入样例2：

```text
5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7
```

输出样例2：

```text
3 3
```

样例解释

样例1：

![[19_0250799aef-1-ee7c9bd4.png]]

样例2：

![[image-1b64e19c.png]]

## 思路分析

暴搜所有一个点之间所有高度相等的点，如果周围的点都高于或低于当前点，那么这个就是一个山谷或山峰

![[PixPin_2024-04-07_12-10-34-1937ea13.gif]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=1010;

int h[N][N];

bool st[N][N];

int n;

int dx[8]={-1,-1,0,1,1,1,0,-1};

int dy[8]={0,1,1,1,0,-1,-1,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=n-1;

}

void dfs(int x,int y,bool &havehigher,bool &havelower){

	for(int i=0;i<8;i++){

		int nx=x+dx[i],ny=y+dy[i];

		if(isVaild(nx,ny)){

			if(h[nx][ny]>h[x][y])

				havehigher=true;

			if(h[nx][ny]<h[x][y])

				havelower=true;

			if(h[nx][ny]==h[x][y] && !st[nx][ny]){

				st[nx][ny]=true;

				dfs(nx,ny,havehigher,havelower);

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	for(int i=0;i<n;i++){

		for(int j=0;j<n;j++){

			cin>>h[i][j];

		}

	}

	int peak=0,valley=0;

	for(int i=0;i<n;i++){

		for(int j=0;j<n;j++){

			if(!st[i][j]){

				bool havehigher=false,havelower=false;

				st[i][j]=true;

				dfs(i,j,havehigher,havelower);

				if(!havehigher)//如果旁边没有更高的 它就是峰地

					peak++;

				if(!havelower)//如果旁边没有更矮的 它就是谷底

					valley++;

			}

		}

	}

	cout<<peak<<" "<<valley<<endl;

	return 0;

}
```

八方向还可以这样写

```cpp
#include <iostream>

using namespace std;

const int N = 1010;

int n;

int h[N][N];

bool st[N][N];

void dfs(int x, int y, bool& has_higher, bool& has_lower) {

    st[x][y] = true;  // 标记当前点已访问

    for (int i = x - 1; i <= x + 1; i++) {

        for (int j = y - 1; j <= y + 1; j++) {

            if (i < 1 || i > n || j < 1 || j > n) continue;

            if (h[i][j] > h[x][y]) has_higher = true;

            else if (h[i][j] < h[x][y]) has_lower = true;

            else if (!st[i][j]) dfs(i, j, has_higher, has_lower);

        }

    }

}

int main() {

    cin >> n;

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= n; j++)

            cin >> h[i][j];

    int peak = 0, valley = 0;

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= n; j++) {

            if (!st[i][j]) {

                bool has_higher = false, has_lower = false;

                dfs(i, j, has_higher, has_lower);

                if (!has_higher) peak++;

                if (!has_lower) valley++;

            }

        }

    }

    cout << peak << ' ' << valley << endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[城堡问题|城堡问题]] 🏠 [[00-刷题理模型]] ➡️ [[残垣断壁|残垣断壁]]